#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

/*
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 *
 * 示例 1:
 *   输入: s = "cbaebabacd", p = "abc"
 *   输出: [0,6]
 *   解释:
 *     起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 *     起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 *
 * 示例 2:
 *   输入: s = "abab", p = "ab"
 *   输出: [0,1,2]
 *   解释:
 *     起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 *     起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 *     起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 *
 * 提示:
 *   1 <= s.length, p.length <= 3 * 104
 *   s 和 p 仅包含小写字母
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

bool compare(int *a, int aSize, int *b, int bSize)
{
    if (aSize != bSize)
    {
        return false;
    }
    int i = 0;
    for (; i < aSize; i++)
    {
        if (a[i] != b[i])
        {
            return false;
        }
    }
    return true;
}

int *findAnagrams(char *s, char *p, int *returnSize)
{
    int capacity = 4096;
    int *ret = (int *)malloc(capacity), *_ret = NULL;
    int pFrequencyArray[26] = {0};
    int sFrequencyArray[26] = {0};
    int subStringSize = 0;
    char *_p = p, *_s = s;
    int left = 0;
    *returnSize = 0;
    while (*_p != 0 && *_s != 0)
    {
        pFrequencyArray[*_p - 'a']++;
        sFrequencyArray[*_s - 'a']++;
        subStringSize++;
        _p++;
        _s++;
    }

    if(*_p != 0 && *_s == 0)
    {
        return ret;
    }

    if (compare(sFrequencyArray, 26, pFrequencyArray, 26))
    {
        ret[*returnSize] = 0;
        (*returnSize)++;
    }

    while (*_s != 0)
    {
        sFrequencyArray[*_s - 'a']++;
        sFrequencyArray[*(s + left) - 'a']--;
        if (compare(sFrequencyArray, 26, pFrequencyArray, 26))
        {
            if (*returnSize == capacity / 4)
            {
                capacity += 4096;
                _ret = ret;
                ret = (int *)malloc(capacity);
                memcpy(ret, _ret, (*returnSize)*4);
                free(_ret);
                _ret = NULL;
            }
            ret[*returnSize] = _s - s + 1 - subStringSize;
            (*returnSize)++;
        }
        _s++;
        left++;
    }
    return ret;
}

int main()
{
    int i;
    int retSize = 0;
    int *ret = findAnagrams("cbaebabacd", "abc", &retSize);
    printf("[");
    for (i = 0; i < retSize; i++)
    {
        printf("%d ", ret[i]);
    }
    printf("]\n");
    return 0;
}